#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        int dp[201][201] = { {0} };

        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--)
            {
                if (i == m - 1) dp[i][j] = dp[i][j + 1] + dungeon[i][j] > 0 ? 0 : dp[i][j + 1] + dungeon[i][j];
                else if (j == n - 1) dp[i][j] = dp[i + 1][j] + dungeon[i][j] > 0 ? 0 : dp[i + 1][j] + dungeon[i][j];
                else dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]) + dungeon[i][j] > 0 ? 0 : max(dp[i + 1][j], dp[i][j + 1]) + dungeon[i][j];
            }

        return abs(dp[0][0]) + 1;
    }
};